FILENAME: FREEGRAM4.TXT
AUTHOR: Jim Roskind
        Independent Consultant
        516 Latania Palm Drive
        Indialantic FL 32903
        (407)729-4348
        jar@ileaf.com
        or ...uunet!leafusa!jar
        

                                                        6/6/90

Dear C++ and C Grammar User,

I have written a YACC debugging tool, and a set of grammars for C and 
C++ in order to use them within my own personal project  development.  
I  have made my work in this area available to other developers at no 
charge with the hope that they would use  my  work.   I  believe  the 
entire  C++  community can benefit from such standardization.  If any 
of the copyright notices on the grammars  (which  are  VERY  liberal) 
prevent using my work, please notify me of the problem.

Note  that  the  grammars can each be processed by YACC, but they are 
very clean, and make NO USE of the precedence setting  (i.e.:  %prec) 
or  associativity  setting  (i.e.:%assoc)  constructs  of YACC.  This 
feature should make them easily portable to  other  parser  generator 
input  format.  This "cleanliness" fact also provides brutal exposure 
of all the complex constructs in  C++,  and  the  complexity  of  the 
grammar as a whole (the C++ grammar is 2 to 3 times as large as the C 
grammar) reflects this exposure.

The files included in this set are:

    FREEGRM4.TXT    This introductory file
    GRAMMAR4.TXT    Parsing ambiguities in C++, and in my grammar
    CPP4.Y          My YACC compatible C++ grammar
    C4.Y            My YACC compatible, ANSI C conformant grammar
    CPP4.L          Flex input file defining a C++ lexical analyser
    SKELGRPH.C      A hacked file from the Berkeley YACC distribution.

Aside from the addition of several files, this release of my  grammar 
corrects  a  few  problems located in my prior release.  This release 
will hopefully conclude compliance with C++  2.0,  and  allow  me  to 
release a C++ 2.1 compliant grammar (re: nested types).

Since my first public release of my grammar, I have received a number 
of requests.  One of the most  common  requests  was  for  a  lexical 
analyser  to  go  with  the  grammar.   This  release  of the grammar 
provides such a a "bare bones" lexical analyser.  The  analyser  does 
not  support  preprocessing,  or  even comment removal.  In addition, 
since I have not included a symbol table, or semantic actions in  the 
grammar  to  maintain  proper  context (i.e., current scope), typedef 
names and struct/class/union/enum tags are not *really* defined.   To 
allow  users to experiment with my grammar without a symbol table, my 
lexer assumes that if the first letter of the  name  is  upper  case, 
then  then name is a type name.  This hack is far from sufficient for 
parsing full blown programs, but  it  is  more  than  sufficient  for 
experimenting  with  the  grammar to determine the acceptability of a 
token sequence, and to understand how my grammar parsed the sequence.

Since I did not believe  that  a  lexical  analyser  alone  would  be 
sufficient to assist many people with playing with my grammar, I have 
also provided the basis for a tool  to  explain  what  a  grammar  is 
doing.   Specifically, I have modified a file that is included in the 
Berkeley YACC distribution so that parsers generated by such  a  YACC 
would  automatically  display a syntax tree in graphical-ASCII format 
during a parse.  The instructions for using and  building  this  yacc 
tool  are  presented  in  the  next  section.  Note that there are no 
significant special hooks in my grammar or parser to excite this yacc 
tool,  and  the tool can be used equally well on any grammar that you 
are working with.

I have posted all 6 files to comp.lang.c++, to make this  information 
as  available  as possible to users and developers.  I will also post 
this introductory note to  comp.compilers,  and  comp.lang.c.   I  am 
arranging  for  archival  support  via several ftp sites, and updates 
will be posted to those sites.  I will also try to get the source  to 
Berkeley  YACC  posted  to  these ftp sites, although it is certainly 
available at more central sites.


HOW TO USE THE DISTRIBUTION FILES TO PLAY WITH THE C++ GRAMMAR

Note that  the  following  instructions  assume  that  you  have  the 
Berkeley  YACC  source  on  hand.   You  can actually use any YACC to 
process the grammar, but running the resulting  demo  (which  has  no 
semantic  actions)  will  tend  to be quite boring.  If you can't get 
hold of the Berkeley YACC, you should at  least  try  to  enable  the 
"debugging options" in your parser to so that you can see in some way 
what reductions are taking  place.  (Hint:  search  for  the  letters 
"debug" in the C file that your yacc produces...).

        1) Get the entire source for Berkeley YACC 1.4 2/25/90
        2) Verify that you can make the YACC
        3) Rename SKELETON.C to SKELOLD.C, and implant my SKELGRPH.C
                in that directory as SKELETON.C
        4) Make the yacc using this new SKELETON.C
        5) Using the above yacc, process my CPP4.Y file
                yacc -dvl cpp4.y
           The result should be a file y.tab.c, and y.tab.h
        6) Using Flex (replacement for lex) process my CPP4.L file
                flex cpp4.l
           the result should be yy.lex.c
        7) Compile the two files
                cc -o cpp4  y.tab.c yy.lex.c
           the result should be an executable called cpp4
        8) Set the environment variable YYDEBUG to 6
                setenv YYDEBUG 6
           If you don't do this, the graphical output will not appear!
        9) Run the program cpp4
                cpp4
        10) Try the input:
                int a;
        11) You should see a nice parse tree.  Enjoy.  Note that
            the lexer DOES NOT INCLUDE A SYMBOL TABLE, and does
            NOT KEEP TRACK OF CURRENT SCOPES.  The hack (see the
            CPP4.L file for details) is to assume that any identifier
            that begins with a capital letter is a typedef name
            Send complaints about code that doesn't parse "correctly".


INTRODUCTION TO 3/3/90 Version of my release

In   light   of   the   recent  debate  on  comp.lang.c++  about  the 
"impossibility" of generating a YACC grammar for  C++  (that  doesn't 
also  accept  every  possible  string  of  tokens),  providing  these 
grammars at this point is especially nice.   Rather  than  addressing 
each of the ad hoc arguments that such an endeavor is impossible (the 
least convincing  of  which  said  effectively:  "...  heard  it  was 
impossible,  ...  something  about LALR ...", and the most correct of 
which said: "...it is not possible to create a  simple  YACC  grammar 
for  C++.."),  I  am  offering  my  grammars  as  my  rather complete 
commentary on the topic. (I'll probably get some flaming due to  this 
comment,  but  I had to read all the stuff that was posted, that told 
me what I had done was impossible. ;-) ) My general feeling  is  that 
it  is  a  shame  for  opinions  to  be  confused with facts, and for 
impossibility to be confused with difficulty or complexity.

Developing the C grammar (that is intended to be compatible with  the 
ANSI C standard) was relatively straight forward (compared to the C++ 
grammar).  The one difficulty in this process was the desire to avoid 
use  of  %prec  and  %assoc  constructs  in YACC, which would tend to 
obscure ambiguities.  Since I didn't know what ambiguities were lying 
in  wait  in  C++,  obscuring  ambiguities was unacceptable.  It took 
several weeks to remove the conflicts that typically appear, and  the 
tedious  process  exposed  several ambiguities that are not currently 
disambiguated by the ANSI standard.  The quality of the C grammar  is 
(IMHO)  dramatically  higher than what has been made available within 
the  public  domain.   Specifically,  a  C   grammar's   support   of 
redefinition of typedef names within inner scopes (the most difficult 
area of  the  grammar)  is  typically  excluded  from  public  domain 
grammar,  and  even  excluded  from  most  grammars that are supplied 
commercially with parser generators!  I expect that this grammar will 
be very useful in the development of C related tools.

The development of the C++ grammar (initially compatible with version 
1.2, but enhanced to support version 2.0 specifications as they  were 
made  available)  was anything but straight forward.  The requirement 
that I set to NOT USE %prec and %assoc proved both a blessing  and  a 
curse.   The  blessing was that I could see what the problems were in 
the language, the curse was that there were A LOT of conflicts (I can 
recall  times  during  the  development  effort  when  the  number of 
conflicts was well in excess of 200).  Initially I was  unaware  that 
many  other  attempts  had  been  made  and  failed, and I went ahead 
"blindly" trying to resolve  the  conflicts  in  my  grammar.   After 
raising  the  issues  that I noticed with Bjarne Stroustrup, I became 
aware that there were some very significant  syntactical  ambiguities 
within  the  current  C++ language.  Fortunately, by the time I first 
spoke to Dr. Stroustrup, I had  already  derived  some  results  that 
other  attempts  had  not  uncovered.   Encouraged  by  my results, I 
continued on despite hearing ever louder  claims  that  my  goal  was 
"impossible".

Towards  the  end  of  the development of the C++ grammar, which took 
roughly 3 months of my time, I began to see the folly in part  of  my 
quest.   I  came to the conclusion that further attempts to modify my 
grammar, so as to defer resolutions of ambiguities, would lead to  an 
unreadable language. Specifically, my feeling was that I was entering 
into a battle of  wits  with  the  compiler,  and  the  compiler  was 
starting  to  win.   It  was beginning to be the case that the parser 
COULD figure out what I said, but I couldn't.  Indeed, even  examples 
in  a  version  of  the  C++  2.0  reference manual demonstrated this 
problem (my parser could parse some examples that neither I  nor  the 
authors parsed correctly!).  At this point I decided to stop my quest 
to FURTHER defer resolutions of  ambiguities,  and  let  the  grammar 
commit  in  one  direction  (always in favor of declarations), at the 
late point that is provided by my grammar.  If this direction  proved 
"incorrect in light of the context that followed", then I generated a 
syntax error.  I  believe  this  strategy  provides  ample  room  for 
expressiveness.  In  support of this expressiveness, I have (based on 
my discussions with language  experts)  deferred  disambiguation  far 
longer  than  other  attempts at producing an LR(1) grammar.  I would 
strongly argue that any code that my grammar identifies as  having  a 
"syntax  error"  (based  on  "premature"  disambiguation), but cfront 
allows, should ABSOLUTELY be rewritten in a less ambiguous (and hence 
more portable) form.  As a final comment, by virtue of the consistent 
methodology used to build my grammar, there are a number  of  clearly 
unambiguous  constructs  that  my  grammar  CAN parse, and cfront 2.0 
cannot (not to mention recent versions of GNU's G++ and Zortech's C++ 
compiler).

One  major  motivation for using the C++ grammar that I have provided 
is that it is capable of supporting old  style  function  definitions 
(e.g.:  main(argc,  argv)  int  argc;  char*argv[];  {...}  ).  To my 
knowledge, no other C++ parser is currently capable of this  feat.  I 
believe  this  capability  was  removed from the C++ specification in 
order to reduce ambiguities in a specific implementation (cfront). As 
my  grammar  demonstrates,  this action was not necessary. Supporting 
old style function definition GREATLY eases the transition to the use 
of  C++  from  traditional C.  I expect that as some parsers begin to 
support this option, that other parsing engines  will  be  forced  in 
this  direction  by a competitive marketplace.  Using my grammar, and 
the standards it  implies,  appears  to  be  a  very  straightforward 
approach to this support.

A  second motivation for using my grammar is that it can be processed 
by YACC.  The advantage in this fact lies with YACC's  capability  to 
identify  ambiguities.   For  software manufacturers that are heavily 
concerned with correctness, this  is  an  INCREDIBLE  advantage.   My 
experience  with  hand  written  parsers  (which  usually represent a 
translation by a fallible human from a grammar to  parsing  code)  is 
that  they evolve and become more correct with time.  Ambiguous cases 
are often misparsed, without the author ever realizing  there  was  a 
conflict!  In  contrast,  either  a  YACC  grammar  supports  a given 
construct, or it doesn't.  If a YACC grammar  supports  a  construct, 
the  semantic interpretation is usually rather straight forward.  The 
likelihood  of  internal  errors   in   the   parser   is   therefore 
SIGNIFICANTLY  reduced. The fact the the grammars I supplied are free 
of %assoc  and  %prec  operators,  implies  the  grammar  are  fairly 
portable,  and  the  conflicts  are open to peer code review (and not 
obscured).

If you find any errors in my grammars, I would be DELIGHTED  to  hear 
mention  of  them!!!!   These  should  fall into one of the following 
categories:

        1) The grammar left out the following features of C++...
        or
        2) The grammar mis-parses the following sequences...
        or
        3) The discussion of the following ambiguity is
        incorrect...
        4) The grammar could be simplified as follows...

Please send correspondence of this form to jar@ileaf.com. My response 
to  1's  will  be  to add the feature (if possible!); feel sad that I 
made a mistake; and feel glad that YOU  found  it.   I  will  have  a 
similar  response  to  2's.   Responses  of  type  3 are GREAT, but I 
haven't found many folks that really get into YACC ambiguities, so  I 
have  low expectations... feel free to surprise me!!! :-) :-).  Items 
of type 3 are interesting, but since simplicity is in the eye of  the 
beholder,  such  suggestions  are  subject  to  debate.   I  would be 
interested in seeing suggestions in this  area  with  the  constraint 
that  they  do  not  increase the number of conflicts in the grammar!  
Please use YACC to check your suggestions before submitting them. (It 
is  often  AMAZING how the slightest change in the grammar can change 
the number of conflicts, and it took a great deal of  work  to  reach 
the current state). Distribution site(s) will be set up to distribute 
updates  and  or  corrections.   Postings  about  the   presence   of 
corrections will be made on the net.

Since  the  two  grammars (C and C++) were generated in parallel, you 
should  be  able  to  compare  non-terminals  directly.   This   will 
hopefully  make  it easier to identify the complexities involved with 
the C++ grammar, and "ignore" those that result from standard ANSI C. 
In  both  cases I have left the standard if-if-else ambiguity intact. 
In the case of ANSI C grammar, this is the only shift-reduce conflict 
in  the grammar.  Although there are a number of conflicts in the C++ 
grammar, there are actually very few classes of problems. In order to 
disambiguate  the C++ grammar enough that YACC can figure out what to 
do, I was commonly forced to "inline expand" non-terminals  found  in 
the  C  grammar.  This expansion allowed YACC to defer disambiguation 
until it was possible for an LR(1) parser to understand the  context. 
The  unfortunate  consequence  of  this  inline  expansion is a large 
growth in the number of rules,  and  the  presence  of  an  effective 
"multiplier" in most cases where conflicts do occur. As a result, any 
conflicts that arise are multiplied by a factor corresponding to  the 
number  of  rules  I  had to list separately.  I have grouped the C++ 
grammar conflicts in the "Status" section of the  GRAMMAR.TXT  paper, 
but  you  are  welcome to explore my grammars using YACC directly (be 
warned that you will need a robust version of YACC to handle the  C++ 
sized  grammar).  PLEASE do not be put off by the number of conflicts 
in the C++ grammar.  There are VERY FEW CONFLICTS, but my  elaborated 
grammar confuses the count.

The  GRAMMAR4.TXT  paper is FAR from a publishable quality paper, but 
it discusses many  of  the  issues  involved  in  ambiguities  in  my 
grammar,  and more generally in the C++ language. I hope GRAMMAR4.TXT 
it is a vast improvement over "nothing  at  all",  but  apologize  in 
advance  for  lack  of  polished  structure, and the presence of many 
typos  (which  must  surely  be  present).  I  hope  you  find   this 
almost-paper  interesting.  My attempts at documenting conflicts have 
certainly clarified the problems in my mind. Based on  my  experience 
with  the  conflicts  I  have  identified, most current compilers and 
translator fall prey to the situations that I have uncovered.  I hope 
that other compilers, that do not make use of the grammar I have made 
available, will at least seek to standardize the  resolution  of  the 
problems identified.

As  a  small commercial message... I am a freelance consultant, and I 
travel far and wide to perform contracts.  If you like the work  that 
I  am  presenting in this group of documents, and would like to see a 
resume or at least talk, please feel free to contact me.

I hope that the grammars that I have  provided,  will  lead  to  many 
successful C++ processing projects.

Jim Roskind
Independent Consultant
516 Latania Palm Drive
Indialantic FL 32903
(407)729-4348
jar@ileaf.com
or ...!uunet!leafusa!jar